package com.baosight.xCyber;

import java.util.LinkedList;
import java.util.logging.Logger;

public class TrieTree {
    private TrieNode root = new TrieNode();
    private Logger log = Logger.getLogger(TrieTree.class.getSimpleName());

    class TrieNode {
        TrieNode preNode = null;    //获取父节点
        boolean isEnd = false;  //尾字符标识
        int deep = 0;       //做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
        char content = 0;   //当前节点的字符
        LinkedList<TrieNode> child = new LinkedList<>();    //获取子节点

        TrieNode() {
        }

        TrieNode(char content) {
            this.content = content;
        }

        @Override
        public String toString() {
            return "\n" + "{" + "End=" + isEnd + ", d=" + deep + ", c=" + content + ", c=" + child + '}';
        }

        @Override
        public int hashCode() {
            return content + deep;
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof TrieNode && (((TrieNode) obj).content == content);
        }

        void setPreNode(TrieNode node) {
            preNode = node;
        }

        TrieNode getPreNode() {
            return preNode;
        }


        /**
         * child中是否有此Node
         *
         * @param character 保存的char
         * @return 存在返回不存在返回Null
         */
        TrieNode getNode(Character character) {
            for (TrieNode aChild : child) {
                if (aChild.content == character) {
                    return aChild;
                }
            }
            return null;
        }
    }

    /**
     * 添加一个word
     * apple
     *
     * @param word 需要添加的词
     */
    public void addWord(String word) {
        int deep = 0;
        //初始化TrieNode
        TrieNode currNode = root;
        while (deep < word.length()) {
            /*
             * 判断当前node的child，如果为空直接添加，不为空，查找是否含有，不含有则添加并设为currNode，含有则找到并设置为currNode
             */
            char c = word.charAt(deep);
            //判断当前字符是否在其子节点字符中
            if (currNode.child.contains(new TrieNode(c))) {
                //若是，则设置下次循环的主节点为当前字符
                currNode = currNode.getNode(c);
            } else {
                //若不是，则新建节点：设置其父节点为根节点,并添加至根节点的子节点
                //深度+1
                //设置下次循环的主节点为当前字符
                TrieNode node = new TrieNode(c);
                node.setPreNode(currNode);
                node.deep = deep + 1;
                currNode.child.add(node);
                currNode = node;
            }
            //判断当前字符是否已经遍历完毕
            if (deep == word.length() - 1) {
                currNode.isEnd = true;
            }
            deep++;
        }
    }

    /**
     * word在map中是否存在
     *
     * @param word 需要查找的word
     * @return 是否存在
     */
    public boolean hasWord(String word) {
        int deep = 0;
        TrieNode currNode = root;
        while (deep < word.length()) {
            char c = word.charAt(deep);
            if (currNode.child.contains(new TrieNode(c))) {
                currNode = currNode.getNode(c);
            } else {
                return false;
            }
            if (deep == word.length() - 1) {
                return currNode.isEnd;
            }
            deep++;
        }
        return false;
    }


    /**
     * 前序遍历所有节点
     */
    public void traverseTree() {
        visitNode(root, "");
    }

    private void visitNode(TrieNode node, String result) {
        log.info("node.content->" + node.content);
        String re = result + node.content;
        for (TrieNode n : node.child) {
            visitNode(n, re);
//            log.info("result->" + re);
            System.out.println(re);
        }
    }

    public static void main(String[] args) {
        String str[] = {"a", "app"};
        TrieTree tree = new TrieTree();
        for (String s : str) {
            tree.addWord(s);
        }
        //tree.addWord("word");
        tree.traverseTree();
    }


//    //第一个参数，需要生成树的数组，第二个参数为树的根节点
//    public JSONObject getJsontree(JSONArray json, JSONObject job){
//        JSONArray tempJson = JSONArray.fromObject("[]");
//        //筛选出父id等于job里面id的科室
//        for(int i = 0;i < json.size();i++)
//        {
//            //这里可以使用Iterator
//            if(json.getJSONObject(i).get("parent_id").equals(job.get("unit_sn"))) {
//                tempJson.add(json.getJSONObject(i));
//            };
//        }
//        // 优化，减少科室集合的数量，避免重复查询，有再优化的方法，希望告知。。
//        json.removeAll(tempJson);
//        for(int i = 0;i < tempJson.size(); i ++) {
//            //对第二层进行递归，此处类推
//            getJsontree(json, tempJson.getJSONObject(i));
//        }
//        //生成完的树结构map集合加到根节点
//        if(tempJson.size()!=0)
//            job.put("children", tempJson);
//        return job;
//    }

//    /**
//     *
//     * @param word 需要查找的word
//     * @return 是否存在
//     */
//    public boolean hasWord(String word) {
//        int deep = 0;
//        BuilderTree.TrieNode currNode = root;
//        while (deep < word.length()) {
//            char c = word.charAt(deep);
//            if (currNode.child.contains(new BuilderTree.TrieNode(c))) {
//                currNode = currNode.getNode(c);
//            } else {
//                return false;
//            }
//            if (deep == word.length() - 1) {
//                return currNode.isEnd;
//            }
//            deep++;
//        }
//        return false;
//    }
//
//
//
//    public void traverseTree() {
//        //visitNode(root, "");
//        LinkedList<BuilderTree.TrieNode> child = root.getChild();
//        System.out.println(child);
//    }
//
//    /**
//     * 前序遍历所有节点
//     */
//    private void visitNode(BuilderTree.TrieNode node, String result) {
//        log.info("node.content->" + node.content);
//        String re = result + node.content;
//        for (BuilderTree.TrieNode n : node.child) {
//            visitNode(n, re);
//            log.info("result->" + re);
//            System.out.println(re);
//        }
//
//    }
}
